//
// Created by mac on 1/29/22.
//

#include <vector>
#include <iostream>
#include <math.h>
using namespace std;

/*
快排 单端扫描

 */
void quick1Sort(vector<int> &nums, int start, int end){
    if(start>end){ return;}

    int pivot = nums[start];//最左边的元素作为基数
    int left = start;
    int right = start+1;
    while (right<=end){
        if(nums[right]<=pivot){
            left++;
            swap(nums[left], nums[right]);
            right++;//right继续向前，扫描下一个
        } else{
            right++;//大于pivot的元素增加一个
        }
    }
    //nums[left]及nums[left]以前的都小于等于pivot
    //循环结束后nums[left+1]及它以后的都大于pivot
    //所以交换nums[start]和nums[left],这样我们就将中轴元素放到了适当的位置
    swap(nums[start], nums[left]);

    quick1Sort(nums, start, left-1);
    quick1Sort(nums, left+1, end);

}
/*
 二分快排思路 两端扫描， 一端挖坑，另一端填补
 1. 先从数列中取出一个数作为基准数(通常取第一个数)。
 2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
 3. 再对左右区间重复第二步，直到各区间只有一个数。
 */

void  quick2Sort(vector<int> &nums, int start, int end){
    if(start>end){ return;}

    int left = start;
    int right = end;
    int pivot = nums[left];

    while (left<right){
        //从右往左 下面面两个循环的位置不能颠倒，因为第一次坑的位置在最左边
        while (left<right && nums[right]>=pivot){right--;}

        //填A[left]这个坑,填完后A[right]是个坑
        //注意不能是A[left++] = A[right],当因left==right时跳出上面的循环时
        //坑为i和j共同指向的位置,执行A[left++] = A[right],会导致left比right大1，
        //当右边的数据小于基数值时，调换位置
        if(left<right){
            nums[left] = nums[right];
            left++;
        }

        //从左往右 下面面两个循环的位置不能颠倒，因为第一次坑的位置在最左边
        while (left<right && nums[left]<=pivot){left++;}
        if(left<right){
            nums[right] = nums[left];
            right--;
        }

        nums[left] = pivot;
    }

    quick2Sort(nums, start, left-1);
    quick2Sort(nums, left+1, end);
}

/*
 二分快排思路 两端扫描， 一端交换
 1. 先从数列中取出一个数作为基准数(通常取第一个数)。
 2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
 3. 再对左右区间重复第二步，直到各区间只有一个数。
 */
void  quick2_1Sort(vector<int> &nums, int start, int end){
   if(start>end){ return;}

   int pivot = nums[start];
   int left = start;
   int right = end;

   while (left<=right){
       //当left == right时，left和right同时指向的元素还没有与中轴元素判断，
       //小于等于中轴元素，left++,大于中轴元素right--,
       //当循环结束时，一定有left = right+1, 且i指向的元素大于中轴，j指向的元素小于等于中轴

       while (left<=right && nums[left]<=pivot){left++;}

       while (left<=right && nums[right]>=pivot){right--;}
       //当 left > right 时整个切分过程就应该停止了，不能进行交换操作
       //这个可以改成 left < right， 这里 left 永远不会等于right， 因为有上述两个循环的作用

       if(left<=right){
           swap(nums[left], nums[right]);
           left++;
           right--;
       }
   }

   swap(nums[start], nums[right]);
   quick2_1Sort(nums, start, right-1);
   quick2_1Sort(nums, right+1, end);
}


/*
 *
三分快排思路：
三路快排则是将数组分成了小于v，等于v，大于v的三个部分，当递归处理的时候，遇到等于v的元素直接不用管，只需要处理小于v，大于v的元素就好了
 */

void quick3Sort(vector<int> &nums, int start, int end){
    // 对于小规模数组, 使用插入排序会更加快速
    if(start>=end){
        return;
    }


    /* 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot*/
//    swap( arr, left, (int)(Math.random()*(right-left+1)) + left );


    int pivot=nums[start];
    int lt=start;
    int gt=end+1;
    int i=start+1;
    while(i<gt)
    {
        if(nums[i]<pivot){
            swap(nums[i],nums[lt+1]);
            lt++;
            i++;
        }
        else if(nums[i]>pivot){
            swap(nums[i],nums[gt-1]);
            gt--;
        }
        else{
            i++;
        }
    }


    swap(nums[start], nums[lt]);
    quick3Sort(nums,start,lt-1);
    quick3Sort(nums,gt,end);

}




int main(){

    vector<int> num = {2,6,2,5,1,8,32,22,7};
    // quick1Sort(num, 0, num.size()-1);
    // quick2Sort(num, 0, num.size()-1);
//    quick2_1Sort(num, 0, num.size()-1);
       quick3Sort(num, 0, num.size()-1);
    for(int n:num){
        cout<<n<<endl;
    }

}





